package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.ListNode;

/**
 * 删除链表的重复节点
 *
 * @author yuhushuan
 * @date 2020/6/14 10:22
 */
public class _18_2_DeleteDuplicatedNode {
    public static void main(String[] args) {
        ListNode head;

        // 功能测试
        // 重复的节点位于链表的头部
        System.out.println("重复的节点位于链表的头部");
        head = ListNode.Companion.create(new int[]{1, 1, 2, 3, 4, 4, 5});
        assert head != null;
        System.out.println(head.toList());
        System.out.println(deleteDuplicatedNode(head).toList());
        // 中间
        System.out.println("重复的节点位于链表的中间");
        head = ListNode.Companion.create(new int[]{1, 2, 3, 3, 4, 4, 5});
        assert head != null;
        System.out.println(head.toList());
        System.out.println(deleteDuplicatedNode(head).toList());
        // 尾部
        System.out.println("重复的节点位于链表的尾部");
        head = ListNode.Companion.create(new int[]{1, 2, 3, 3, 4, 4, 5, 5});
        assert head != null;
        System.out.println(head.toList());
        System.out.println(deleteDuplicatedNode(head).toList());
        // 链表中没有重复的节点
        System.out.println("链表中没有重复的节点");
        head = ListNode.Companion.create(new int[]{1, 2, 3, 3, 4, 5});
        System.out.println(head);
        System.out.println(deleteDuplicatedNode(head).toList());

        // 特殊输入测试
        // 指向链表头节点为 null
        System.out.println("指向链表头节点为 null");
        System.out.println(deleteDuplicatedNode(null));
        // 链表中所有节点都是重复的
        System.out.println("链表中所有节点都是重复的");
        head = ListNode.Companion.create(new int[]{3, 3, 3, 4, 4, 5, 5});
        System.out.println(head);
        ListNode result = deleteDuplicatedNode(head);
        if (result != null) {
            System.out.println("result:" + result.toList());
        } else {
            System.out.println("result: null");
        }
    }


    private static ListNode deleteDuplicatedNode(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode newHead = null;
        ListNode preNode = null;
        ListNode current = head;
        ListNode nextNode;
        // 遍历链表
        while (current != null) {
            nextNode = current.getNext();
            // 如果当前和下一个节点不相等
            if (nextNode != null && nextNode.getValue() != current.getValue()) {
                if (preNode == null) {
                    newHead = current;
                }
                preNode = current;
            }
            // 如果当前和下一节点相等，current 和 nexNode 都要删除
            if (nextNode != null && nextNode.getValue() == current.getValue()) {
                while (nextNode != null && nextNode.getValue() == current.getValue()) {
                    current = nextNode;
                    nextNode = current.getNext();
                }
                if (preNode != null) {
                    preNode.setNext(nextNode);
                }
            }
            current = current.getNext();
        }
        return newHead;
    }
}